LeetCode 23、合并K个升序链表（优先队列思路）

一、题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[] 

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：278166530
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 合并K个升序链表（LeetCode 23）（优先队列做法）:https://leetcode.cn/problems/merge-k-sorted-lists/
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {

        // 队列是遵循先进先出（First-In-First-Out）模式的，但有时需要在队列中基于优先级处理对象。
        // PriorityQueue 和队列 Queue 的区别在于 ，它的出队顺序与元素的优先级有关
        // 对 PriorityQueue 调用 remove() 或 poll() 方法 ，返回的总是优先级最高的元素
        // Java 中 PriorityQueue 通过二叉小顶堆实现
        // PriorityQueue 默认是一个【小顶堆】，可以通过传入自定义的 Comparator 函数来实现【大顶堆】
        Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);

        // 遍历所有链表
        for (ListNode node: lists) {
            // PriorityQueue 实现了 Queue 接口，不允许放入 null 元素
            if (node != null) {
                // 把所有链表都加入到优先队列当中
                // 优先队列会自己处理，把头节点最小的值放到前面去
                pq.offer(node);
            }

            // ListNode node = pq.peek();

            // System.out.println(node.val);
        }


        // 添加一个虚拟头节点（哨兵），帮助简化边界情况的判断
        ListNode dummyHead = new ListNode(-1);

        // 合并成功之后的尾节点位置
        ListNode tail = dummyHead;

        // 遍历优先队列，取出最下值出来
        while (!pq.isEmpty()) {

            // 取出优先队列，即二叉堆的头节点，最小的节点
            ListNode minNode = pq.poll();

            // 把这个节点连接到合并链表的尾部
            tail.next = minNode;

            // tail 的位置也随之发生变化
            tail = minNode;

            // PriorityQueue 实现了 Queue 接口，不允许放入 null 元素
            if (minNode.next != null) {
                // 再把新的节点也加入到优先队列当中
                pq.offer(minNode.next);
            }
        }

        // 整个过程其实就是「多路归并」过程
        // 返回结果
        return dummyHead.next;
    }
}

**2、C++ **代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：278166530
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 合并K个升序链表（LeetCode 23）（优先队列做法）:https://leetcode.cn/problems/merge-k-sorted-lists/
class Solution {
public:
    struct Status {
        int val;
        ListNode ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    // 队列是遵循先进先出（First-In-First-Out）模式的，但有时需要在队列中基于优先级处理对象。
    // PriorityQueue 和队列 Queue 的区别在于 ，它的出队顺序与元素的优先级有关
    // 对 PriorityQueue 调用 remove() 或 poll() 方法 ，返回的总是优先级最高的元素
    priority_queue <Status> pq;

    ListNode mergeKLists(vector<ListNode*>& lists) {

        
        // 遍历所有链表
        for (auto node: lists) {
            // 把所有链表都加入到优先队列当中
            // 优先队列会自己处理，把头节点最小的值放到前面去
            if (node) pq.push({node->val, node});
        }


        // 添加一个虚拟头节点（哨兵），帮助简化边界情况的判断
      

        // 合并成功之后的尾节点位置
        ListNode dummyHead, *tail = &dummyHead;

        // 遍历优先队列，取出最下值出来
        while (!pq.empty()) {

            // 取出优先队列，即二叉堆的头节点，最小的节点
            auto f = pq.top(); pq.pop();

            // 把这个节点连接到合并链表的尾部
            tail->next = f.ptr; 

            // tail 的位置也随之发生变化
            tail = tail->next;

            // PriorityQueue 实现了 Queue 接口，不允许放入 null 元素
            if (f.ptr->next) pq.push({f.ptr->next->val, f.ptr->next});
        }

        // 整个过程其实就是「多路归并」过程
        // 返回结果
        return dummyHead.next;
    }
};

3、Python 代码

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists or len(lists) == 0:
            return None
        import heapq
        heap = []
        # 和 Java有所不同，是将所有元素都取出放入堆中
        for node in lists:
            while node:
                heapq.heappush(heap, node.val)
                node = node.next
        # 添加一个虚拟头节点（哨兵），帮助简化边界情况的判断 
        dummy = ListNode(None)
        # 合并成功之后的尾节点位置
        tail = dummy
        # 依次将堆中的元素取出(因为是小顶堆，所以每次出来的都是目前堆中值最小的元素），然后重新构建一个列表返回
        while heap:
            temp_node = ListNode(heappop(heap))
            tail.next = temp_node
            tail = temp_node
        return dummy.next